package Aleehot100;

/**
 * ClassName: c033
 * Package: Aleehot100
 * Description: 链表排序 - 148
 *
 * @Author BCXJ
 * @Create 2025/6/24 11:50
 * @Version 1.0
 * @Since 1.0
 */
public class c033 {

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
//    public ListNode sortList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//
//        // 链表的长度n
//        int n = 0;
//        ListNode cur = head;
//        while (cur != null) {
//            cur = cur.next;
//            n++;
//        }
//
//        // 非递归的归并排序
//        ListNode l1, r1, l2, r2, next, preTeamEnd;
//        for (int i = 1; i < n; i <<= 1) {
//            // 第一个整合需要特殊记录，把头结点记录下来
//            l1 = head;
//            r1 = findEnd(l1, i);
//            l2 = r1.next;
//            r2 = findEnd(l2, i);
//            next = r2.next;
//            r1.next = null;
//            r2.next = null;
//            merge(l1, r1, l2, r2);
//            head = start;
//            preTeamEnd = end;
//            while (next != null) {
//                l1 = next;
//                r1 = findEnd(l1, i);
//                l2 = r1.next;
//                if (l2 == null) {
//                    preTeamEnd.next = l1;
//                    break;
//                }
//                r2 = findEnd(l2, i);
//                next = r2.next;
//                r1.next = null;
//                r2.next = null;
//                merge(l1, r1, l2, r2);
//                preTeamEnd.next = start;
//                preTeamEnd = end;
//            }
//        }
//
//        return head;
//
//    }
//
//    public static ListNode start = null;
//    public static ListNode end = null;
//
//    /**
//     * 合并待排序的链表, 确保稳定性
//     */
//    private static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
//        ListNode pre = null;
//        if (l1.val <= l2.val) {
//            start = l1;
//            pre = l1;
//            l1 = l1.next;
//        } else {
//            start = l2;
//            pre = l2;
//            l2 = l2.next;
//        }
//
//        // 归并排序
//        while (l1 != null && l2 != null) {
//            if (l1.val <= l2.val) {
//                pre.next = l1;
//                pre = l1;
//                l1 = l1.next;
//            } else {
//                pre.next = l2;
//                pre = l2;
//                l2 = l2.next;
//            }
//        }
//
//        // 整合剩下的部分
//        if (l1 != null) {
//            pre.next = l1;
//            pre = l1;
//            l1 = l1.next;
//            end = r1;
//        }
//
//        if (l2 != null) {
//            pre.next = l2;
//            pre = l2;
//            l2 = l2.next;
//            end = r2;
//        }
//
//    }
//
//    // 找出链表l1 开头的后面的k个节点
//    private static ListNode findEnd(ListNode head, int i) {
//        while (head.next != null && --i > 0) {
//            head = head.next;
//        }
//        return head;
//    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(3);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        System.out.println(findEnd(listNode1, 2));


        printList(sortList(listNode1));


//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(3);
//        ListNode l3 = new ListNode(5);
//        l1.next = l2;
//        l2.next = l3;
//
//        ListNode l4 = new ListNode(2);
//        ListNode l5 = new ListNode(4);
//        ListNode l6 = new ListNode(6);
//        l4.next = l5;
//        l5.next = l6;
//
//        merge(l1, l4);
    }


    public static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }
    public static ListNode sortList(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }

        // 1 计算链表长度
        int len = 0;
        ListNode node = head;
        while (node != null) {
            len++;
            node = node.next;
        }

        // 2 非递归的归并排序
        ListNode l1, l2, l3, l4, preNext = null, h1 = head, h2;
        for (int i = 1; i < len; i <<= 1) {
            // 头次合并需要记录 h1
            // 分割链表
            l1 = h1;
            l2 = findEnd(l1, i);
            l3 = l2.next;
            l4 = findEnd(l3, i);
            h2 = l4 == null ? null : l4.next;
            l2.next = null;
            l4.next = null;
            merge(l1, l3);
            h1 = start;
            preNext = end;
            while (h2 != null) {
                l1 = h2;
                l2 = findEnd(l1, i);
                l3 = l2.next;
                if (l3 == null) {
                    preNext.next = l1;
                    break;
                }
                l4 = findEnd(l3, i);
                h2 = l4.next;
                l2.next = null;
                l4.next = null;
                merge(l1, l3);
                preNext.next = start;
                preNext = end;
            }
        }
        return start;
    }

    // 找到h1 的第i个节点
    public static ListNode findEnd(ListNode node, int i) {
        while (node.next != null && i > 1) {
            node = node.next;
            i--;
        }
        return node;
    }


    static ListNode start;
    static ListNode end;


    // 3 归并排序的merge方法
    public static void merge(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return;
        }

        start = l1.val < l2.val ? l1 : l2;
        if (start == l1) {
            l1 = l1.next;
        } else {
            l2 = l2.next;
        }

        ListNode preNode = start;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                preNode.next = l1;
                l1 = l1.next;
            } else {
                preNode.next = l2;
                l2 = l2.next;
            }
            preNode = preNode.next;
        }

        while (l1 != null) {
            preNode.next = l1;
            preNode = l1;
            l1 = l1.next;
        }

        while (l2 != null) {
            preNode.next = l2;
            preNode = l2;
            l2 = l2.next;
        }
        end = preNode;
    }

}